package everyday;

import CommonStructure.TreeNode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Author: Siantar
 * @Date: 2023-05-30-14:10
 * @Description: 1.0
 */
public class T1110 {
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        Set<Integer> toDeleteSet = (HashSet<Integer>) Arrays.stream(to_delete).boxed().collect(Collectors.toSet());
        List<TreeNode> res = new ArrayList<>();
        dfs(root, toDeleteSet, res, true, toDeleteSet.contains(root.val));
        return res;
    }

    public void dfs(TreeNode t, Set<Integer> toDeleteSet, List<TreeNode> res, boolean isRoot, boolean willDelete) {
        if (!willDelete && isRoot) res.add(t);
        if (t.left != null) {
            boolean leftWillDelete = toDeleteSet.contains(t.left.val);
            dfs(t.left, toDeleteSet, res, willDelete, leftWillDelete);
            if (leftWillDelete)t.left=null;
        }
        if (t.right != null) {
            boolean rightWillDelete = toDeleteSet.contains(t.right.val);
            dfs(t.right, toDeleteSet, res, willDelete, rightWillDelete);
            if (rightWillDelete)t.right=null;
        }
    }
}
